/**
 * @param {number[]} nums
 * @param {number[][]} edges
 * @return {number}
 */
function minimumScore(nums, edges) {
  const n = nums.length;
  const m = edges.length;

  // 构建邻接表，存储每个节点的邻居和对应的边索引
  const adj = Array.from({ length: n }, () => []);
  for (let i = 0; i < m; i++) {
    const [a, b] = edges[i];
    adj[a].push({ v: b, edgeIdx: i });
    adj[b].push({ v: a, edgeIdx: i });
  }

  // 用于存储DFS过程中的信息
  const parent = new Array(n).fill(-1);
  const xor = new Array(n).fill(0); // 子树异或值
  const inTime = new Array(n).fill(0); // 进入时间（用于判断子树关系）
  const outTime = new Array(n).fill(0); // 离开时间（用于判断子树关系）
  const edgeChild = new Array(m).fill(-1); // 每条边对应的子节点
  let time = 0;

  // DFS遍历计算子树异或值和时间戳
  function dfs(u, p) {
    parent[u] = p;
    inTime[u] = time++;
    xor[u] = nums[u]; // 初始化为当前节点的值

    for (const { v, edgeIdx } of adj[u]) {
      if (v !== p) {
        edgeChild[edgeIdx] = v; // 记录边对应的子节点
        dfs(v, u);
        xor[u] ^= xor[v]; // 累积子树的异或值
      }
    }

    outTime[u] = time++;
  }

  // 从根节点0开始DFS
  dfs(0, -1);
  const totalXor = xor[0]; // 整棵树的异或值

  let minScore = Infinity;

  // 遍历所有可能的两条边组合
  for (let i = 0; i < m; i++) {
    for (let j = i + 1; j < m; j++) {
      const v1 = edgeChild[i];
      const v2 = edgeChild[j];
      const x1 = xor[v1];
      const x2 = xor[v2];

      let a, b, c;

      // 判断两条边的位置关系，计算三个组件的异或值
      if (inTime[v2] > inTime[v1] && inTime[v2] < outTime[v1]) {
        // 情况1：边j在边i的子树中
        a = x2;
        b = x1 ^ x2;
        c = totalXor ^ x1;
      } else if (inTime[v1] > inTime[v2] && inTime[v1] < outTime[v2]) {
        // 情况2：边i在边j的子树中
        a = x1;
        b = x2 ^ x1;
        c = totalXor ^ x2;
      } else {
        // 情况3：两条边在不同的子树中
        a = x1;
        b = x2;
        c = totalXor ^ x1 ^ x2;
      }

      // 计算当前组合的分数并更新最小值
      const currentMax = Math.max(a, b, c);
      const currentMin = Math.min(a, b, c);
      minScore = Math.min(minScore, currentMax - currentMin);
    }
  }

  return minScore;
}

// 测试示例
console.log(
  minimumScore(
    [1, 5, 5, 4, 11],
    [
      [0, 1],
      [1, 2],
      [1, 3],
      [3, 4],
    ]
  )
); // 输出: 9
console.log(
  minimumScore(
    [5, 5, 2, 4, 4, 2],
    [
      [0, 1],
      [1, 2],
      [5, 2],
      [4, 3],
      [1, 3],
    ]
  )
); // 输出: 0
